//给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,0]
//输出：3
//
//
// 示例 2：
//
//
//输入：nums = [3,4,-1,1]
//输出：2
//
//
// 示例 3：
//
//
//输入：nums = [7,8,9,11,12]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 5 * 10⁵
// -2³¹ <= nums[i] <= 2³¹ - 1
//
// Related Topics 数组 哈希表 👍 1507 👎 0

package leetcode.editor.cn;

class 缺失的第一个正数 {
    public static void main(String[] args) {
        Solution solution = new 缺失的第一个正数().new Solution();
        int[] nums = {1, 2, 3, 4, 5, 6, 8, 9, 10};
        System.out.println(solution.firstMissingPositive(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int firstMissingPositive(int[] nums) {
            // l是盯着的位置
            // 0 ~ L-1有效区
            int L = 0;
            int R = nums.length;
            while (L != R) {
                if (nums[L] == L + 1) {
                    L++;
                } else if (nums[L] <= L || nums[L] > R || nums[nums[L] - 1] == nums[L]) { // 垃圾的情况
                    swap(nums, L, --R);
                } else {
                    swap(nums, L, nums[L] - 1);
                }
            }
            return L + 1;
        }

        public void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
